/*
https://www.lintcode.com/problem/dices-sum/description
20. 骰子求和
扔 n 个骰子，向上面的数字之和为 S。给定 Given n，请列出所有可能的 S 值及其相应的概率。

样例
给定 n = 1，返回 [ [1, 0.17], [2, 0.17], [3, 0.17], [4, 0.17], [5, 0.17], [6, 0.17]]。

注意事项
You do not care about the accuracy of the result, we will help you to output results.
*/

/*
解题思路：Hard级别的题目，还是有点难度的，使用动态规划做的。题目是需要得出来投掷N个骰子，所有可能的和的情况，以及概率
例如对于N个骰子，所有和的情况，在区间[N, 6 * N]之间
我们使用vec作为动态规划的保存数据。

例如N=2,和的范围是[2, 12]
和为2有一个情况，两个骰子都是1，概率是两个骰子都是1的概率相乘
和为3有两个情况，(1, 2)和(2, 1), (1,2)的算法就是把一个骰子和为1与和为2的概率相乘，然后把这两个情况的概率想加，得到所有和为3的概率。
.....
和为6有(1, 5) (2, 4) (3, 3) (4, 2) (5, 1) 5种情况，将这5种情况的概率算出来想加。

例如N=3时，和的范围是[3, 18]
这时候我们就不能把3个骰子，按照3个独立个体来算了，这样的话，算法时间复杂度会过高，变成了穷举的算法。动态规划的思想就是利用已经算好的值来迭代运算。
所以N=3时，我们使用N=2的概率与N=1的概率来计算。还是将N=3拆分成两个概率的个体。
例如和为4的情况：(1, 3) (2, 2) (3, 1)计算方法还是和N=2一样，(1,3)->一个骰子和为1的概率乘以2个骰子和为3的概率。然后将所有结果想加得到N=3和为4的情况。
其中（3,1)概率为0，因为两个骰子和为1的概率是0，所以乘积也是0

我们使用vec[n][j]表示n个骰子，和为j的概率
以此类推，N个骰子，我们也拆分成两个概率个体，N-1个骰子的结果和1个骰子的结果。
vec[n][j]=vec[n-1][1] * vec[1][j -1] + vec[n-1][2]*vec[1][j-2] *.........*vec[n-1][j-1]*vec[1][1]
然后通过这个公式，将N从1迭代到需要求得的值。然后返回vec[n]这一行即可
*/
class Solution {
public:
    /**
     * @param n an integer
     * @return a list of pair<sum, probability>
     */
    vector<pair<int, double>> dicesSum(int n) {
        // Write your code here
        vector<vector<double> > vec(1000, vector<double>(1000));
        vector<pair<int, double>> res;
        for (int i = 1; i <= 6; ++i)
        {
            vec[1][i] = 1./6;
        }
        
        for (int i = 2; i <= n; ++i)
        {
            for (int j = i; j <= 6 * i; ++j)
            {
                for (int t = 1; t < j; ++t)
                {
                    vec[i][j] += vec[i - 1][j - t] * vec[1][t];
                }
            }
        }
        for (int i = n; i <= n * 6; ++i)
        {
            res.emplace_back(pair<int, double>(i, vec[n][i]));
        }
        return res;
    }
};